package com.tgy.algorithm._经典题目01;

/**
 * 误虔:一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长例如:
 * 01111
 * 01001
 * 01001
 * 01111
 * 01011
 * 其中边框全是1的最大正方形的大小为4*4，所以返回4。
 */
public class _005_框全是1的最大正方形 {

    public static int maxOneBorderCount(int[][] nums) {

        int row = nums.length;
        int col = nums[0].length;

        int[][] rowOnes = new int[row][col + 1];
        int[][] colOnes = new int[row + 1][col];
        for (int i = 0; i < row; i++) {
            for (int j = col - 1; j >= 0; j--) {
                if (nums[i][j] == 1) {
                    rowOnes[i][j] = rowOnes[i][j+1] + 1;
                }else {
                    rowOnes[i][j] = 0;
                }
            }
        }

        for (int i = row - 1; i >= 0; i--) {
            for (int j = 0; j < col; j++) {
                if (nums[i][j] == 1) {
                    colOnes[i][j] = colOnes[i+1][j] + 1;
                }else {
                    colOnes[i][j] = 0;
                }
            }
        }

        int retLen = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (nums[i][j] == 1) {
                   int maxLen = Math.min(row - i - 1,col - j - 1);
                    for (int k = 0; k <= maxLen; k++) {
                        // [i,j+k] 查询colOnes的下面1的个数
                        // [i+k,j] 查询rowOnes 右边1的个数
                        int moreK = k + 1;
                        if (rowOnes[i][j] >= moreK
                                && colOnes[i][j] >= moreK
                                && colOnes[i][j+k] >= moreK
                                && rowOnes[i+k][j] >= moreK
                        ) {
                            retLen = Math.max(retLen,moreK);
                        }
                    }
                }
            }
        }

        return retLen;
    }

    public static void main(String[] args) {

        int[][] nums = new int[][]{
                {0,1,1,1,1},
                {0,1,0,0,0},
                {0,1,0,1,0}
        };
        int i = maxOneBorderCount(nums);
        System.out.println(i);
    }
}
